#include <vector>
#include <algorithm>

using namespace std;

// 找出第K小的数对距离
// 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
// 给你一个整数数组 nums 和一个整数 k
// 数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
// 返回 所有数对距离中 第 k 小的数对距离。
// 测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

class Solution 
{
private:
    // nums 中任意两数的差值 <= limit
	// 这样的数字配对，有几对？
    int f(vector<int>& nums, int limit)
    {
        int ans = 0, n = nums.size();
        // 滑动窗口：O(n)
        for(int l = 0, r = 0; l < n; ++l)
        {
            // l ... r r+!
            while(r + 1 < n && nums[r + 1] - nums[l] <= limit) ++r;
            // arr[l...r] 范围上的数差值的绝对值都不超过 limit
            // arr[0...3] : (0, 1) (0, 2) (0, 3)
            ans += r - l;
        }
        return ans;
    }

public:
    // 时间复杂度 O(n * log(n) + log(max-min) * n)，额外空间复杂度 O(1)
    int smallestDistancePair(vector<int>& nums, int k) 
    {
        sort(nums.begin(), nums.end());
        int ans = 0, l = 0, r = nums.back() - nums[0];
        // [0, 最大-最小]，不停二分
        while(l <= r)
        {
            // m 中点，nums 中任意两数的差值 <= m
            int m = l + ((r - l) >> 1);
            // 返回数字对的数量
            int cnt = f(nums, m);
            if(cnt >= k)
            {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        return ans;
    }
};